package sword2offer;

import java.util.Arrays;
import java.util.Random;

/**
 * <p>
 * 数组中第K个最大元素
 * </p>
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 *
 * @author LovelyBigDuck
 * @date 2022/3/23 22:16
 */
public class S_215 {
    static class Solution {
        public int findKthLargest(int[] nums, int k) {
            quickSort(nums, 0, nums.length - 1);
            Arrays.stream(nums).forEach(System.out::print);
            return nums[nums.length - k];
        }

        public void quickSort(int[] nums, int left, int right) {
            if (left >= right) {
                return;
            }
            int index = sort(nums, left, right);
            quickSort(nums, 0, index - 1);
            quickSort(nums, index + 1, right);
        }

        public int sort(int[] nums, int left, int right) {
            int key = nums[left];
            while (left < right) {
                while (left < right && nums[right] >= key) {
                    right--;
                }
                nums[left] = nums[right];
                while (left < right && nums[left] <= key) {
                    left++;
                }
                nums[right] = nums[left];
            }
            nums[left] = key;
            return left;
        }

        public static void main(String[] args) {
            int[] nums = {2, 4, 5, 6, 7, 8, 4, 2, 5, 3, 5, 8, 9, 0};
            Solution solution = new Solution();
            int res = solution.findKthLargest(nums, 1);
            System.out.println("\n" + res);
        }
    }
}
